// 中心扩展法

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() <= 1) { return s; }

        int maxLen = 1;
        int begin = 0;
        // 若i从1开始，对于长度为2的字符串可能出错
        for (int i = 0; i < s.size() - 1; ++i) {
            int oddLen = expandArround(s, i, i);
            int evenLen = expandArround(s, i, i + 1);
            int tmp = max(oddLen, evenLen);
            if (maxLen < tmp) {
                maxLen = tmp;
                begin = i - (maxLen - 1) / 2;
            }
        }
        return s.substr(begin, maxLen);
        
    }

    int expandArround(string &s, int left, int right) {
        while (left >= 0 && right < s.size()) {
            if (s[left] != s[right]) { break; }
            left--;
            right++;
        }
        return right - left - 1;
    }
};